-module (osmos_tree).

-export ([ new/1,
	   search/2,
	   insert/3,
	   update/3,
	   total_entries/1,
	   iter_begin/1,
	   iter_end/1,
	   iter_lower_bound/2,
	   iter_next/1,
	   iter_key/1,
	   iter_value/1 ]).

-include ("osmos.hrl").

-record (tree, { less, tree }).
-record (iter, { key, value, iter }).

new (Less) ->
  #tree { less = Less, tree = my_gb_trees:empty () }.

search (#tree { less = Less, tree = Tree }, Key) ->
  case my_gb_trees:lookup (Less, Key, Tree) of
    { value, V } -> { ok, V };
    none         -> not_found
  end.

insert (T = #tree { less = Less, tree = Tree }, Key, Value) ->
  NewTree = my_gb_trees:insert (Less, Key, Value, Tree),
  T#tree { tree = NewTree }.

update (T = #tree { less = Less, tree = Tree }, Key, Value) ->
  NewTree = my_gb_trees:update (Less, Key, Value, Tree),
  T#tree { tree = NewTree }.

total_entries (#tree { tree = Tree }) ->
  my_gb_trees:size (Tree).

iter_begin (#tree { tree = Tree }) ->
  case my_gb_trees:next (my_gb_trees:iterator (Tree)) of
    { K, V, It } -> #iter { key = K, value = V, iter = It };
    none         -> ?ITER_END
  end.

iter_end (_Tree) ->
  ?ITER_END.

iter_lower_bound (Tree, Less) when is_function (Less) ->
  % XXX: inefficient
  iter_lower_bound_scan (iter_begin (Tree), Less);

iter_lower_bound (Tree = #tree { less = Less }, Key)
	when not is_function (Key) ->
  iter_lower_bound_scan (iter_begin (Tree), fun (K) -> Less (K, Key) end).

iter_lower_bound_scan (?ITER_END, _Less) ->
  ?ITER_END;
iter_lower_bound_scan (It, Less) ->
  case Less (iter_key (It)) of
    false -> It;
    true  -> iter_lower_bound_scan (iter_next (It), Less)
  end.

iter_next (#iter { iter = It }) ->
  case my_gb_trees:next (It) of
    { K, V, NewIt } -> #iter { key = K, value = V, iter = NewIt };
    none            -> ?ITER_END
  end.

iter_key (#iter { key = K }) ->
  K.
iter_value (#iter { value = V }) ->
  V.
